The present invention relates generally to approximation of an ordered set of points by a series of geometric elements, and more particularly to approximation of an ordered set of points in which the position of each point is determined with a non-zero accuracy.
In diverse applications, geometric features may be represented as an ordered set of points. In land surveying, roads, rivers, and boundaries of territories may be delineated by ordered sets of points. In computer vision systems, the boundaries of objects may be delineated by ordered sets of points. In digital image processing, the contours of objects in an image may be represented by ordered sets of points (pixels). Analyzing raw sets of points requires computer systems with high power processors, large memory, and complex algorithms. More efficient analysis may be achieved by approximating a set of points with a series of geometric elements. For example, a road may be modelled as a chain (sequence) of segments. Basic segments include straight line segments and circular arcs. If needed, more complex geometric curves may be used to smoothly transition between adjacent segments. In addition to more efficient analysis, approximation by a series of geometric elements provides a mechanism for data compression: the raw set of points may be characterized by a smaller set of geometric parameters. For example, a series of points falling on a straight line segment may be characterized by the coordinates of the two end points of the segment. Similarly, a series of points falling on a circular arc may be characterized by the coordinates of the two end points of the arc and the coordinates of a third point lying on the arc.
Note that a point is a geometric abstraction. In real applications, a particular position may be determined within a non-zero accuracy. In land surveying, for example, accuracy is a function of the resolution and errors in the measurement system (and other factors). In a digital imaging system, accuracy is a function of pixel size of the digital image (and other factors). In data compression, accuracy is a function of the value of acceptable (user-defined) loss of information, which may be described by the compression ratio (and other factors). What is needed is a method for approximating an ordered set of points, in which the position of each point has a non-zero accuracy, with a series of geometric elements.